package leetcode.code1654;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	boolean[] f;
	int a, b, x;

	int max;

	public int minimumJumps(int[] forbidden, int a, int b, int x) {
		this.max = 6000;
		this.f = new boolean[max + 1];
		for (int i = 0; i < forbidden.length; i++) {
			this.f[forbidden[i]] = true;
		}
		this.x = x;
		this.a = a;
		this.b = b;
		int[][] dp = new int[2][max + 1];
		Arrays.fill(dp[0], -2);
		Arrays.fill(dp[1], -2);
		// 从0位置，向前跳最少步数
		dp[0][0] = -3;
		int ans = this.minimumJumps(0, 0, dp);
		return ans;
	}

	private int minimumJumps(int index, int direction, int[][] dp) {
		if (this.f[index]) {
			return -1;
		}
		if (index == this.x) {
			return 0;
		}
		if (dp[direction][index] != -2 && dp[direction][index] != -3) {
			return dp[direction][index];
		}
		int num1 = -1;
		if (index + a < max && dp[0][index + a] == -2) {
			dp[0][index + a] = -3;
			num1 = this.minimumJumps(index + a, 0, dp);
		}
		int num2 = -1;
		if (direction == 0 && index - b > 0 && dp[1][index - b] == -2) {
			dp[1][index - b] = -3;
			num2 = this.minimumJumps(index - b, 1, dp);
		}
		int ans = 1;
		if (num1 == -1 && num2 == -1) {
			ans = -1;
		} else if (num1 != -1 && num2 != -1) {
			ans += Math.min(num1, num2);
		} else if (num1 != -1) {
			ans += num1;
		} else {
			ans += num2;
		}
		dp[direction][index] = ans;
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(1548, this.minimumJumps(H.str2array3("[549, 693, 456, 1814, 1609]"), 748, 889, 545));
		H.compare(3998, this.minimumJumps(H.str2array3("[1998]"), 1999, 2000, 2000));
		H.compare(121, this.minimumJumps(H.str2array3(
				"[162,118,178,152,167,100,40,74,199,186,26,73,200,127,30,124,193,84,184,36,103,149,153,9,54,154,133,95,45,198,79,157,64,122,59,71,48,177,82,35,14,176,16,108,111,6,168,31,134,164,136,72,98]"),
				29, 98, 80));
		H.compare(2, this.minimumJumps(H.str2array3("[1,6,2,14,5,17,4]"), 16, 9, 7));
		H.compare(-1, this.minimumJumps(H.str2array3("[8,3,16,6,12,20]"), 15, 13, 11));
		H.compare(3, this.minimumJumps(H.str2array3("[14,4,18,1,15]"), 3, 15, 9));
		H.compare(6, this.minimumJumps(H.str2array3("[128,178,147,165,63,11,150,20,158,144,136]"), 61, 170, 135));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
